#include<vector>
#include<iostream>

using namespace std;

int make_charge(vector<int> &coins, int target) {
  // 保存结果的 ways, 这个数组中的每一个位置，都表示一个需要找出来的零钱值
  // 这样，ways 最后一个位置的值，就是我们想要的答案。
  vector<int> ways(target + 1, 0);
  ways[0] = 1; // 找 0 元只有一种方法

  for (int coin : coins) {
    // 对于每一种面额的硬币
    for (int i = 0; i < target + 1; ++i) {
      // 检查是否可以用它找出 ways 中每一个位置代表的钱数
      if (coin <= i) {
        ways[i] = ways[i - 1] + 1;
      }
    }
  }
  return *ways.rbegin();
}

int main(int argc, char const *argv[])
{
  vector<int> arr {1, 2, 3};
  cout << make_charge(arr, 10) << endl;
  return 0;
}
